Sketch of Solutions

Q1.
If a vertex is chosen ahead of its neighbours it will be in I, 
and the probability that this happens is 1/(deg(v)+1) hence the 
total number of vertices in the cover is at least 

     sum_{v in V}   1/(deg(v)+1)  

Q2.

Sort the vertices in increasing order by degree. The first vertex v1 is in I,
and it eliminates deg(v1) other vertices, each of which had a contribution of
at most 1/(deg(v1)+1) to the expected number of vertices chosen. Continue with
selecting the next vertex of smallest degree and eliminate its neighbours until
there are no vertices left. In other words, in the summation above we selected
deg(v1)+1 terms, converted the largest, i.e. 1/(deg(v1)+1)  to 1 and made the
other deg(v1)  terms which are smaller than 1/(deg(v1)+1)  equal to 0.  So the
total contribution of those terms is 1, whereas in the summation above the
contribution was at most

(deg(v_1 )+1)  x   1/(deg(v_1 )+1)  =  1

So the size of the summation does not change. The same holds for all other
vertices chosen. Hence the size of the independent set found exceeds the
expected size given by the summation. 

Q3a.

We select each vertex with probability xi , then the expected number of points
in the cover is sum xi= k.

Q3b.

If we ignore the y(u,v) variables then we obtain, on the expectation the best
k-cover except for the fact that edges might be double covered. Hence we are
within 1/2 of the actual optimum

Q3c.

[one of various ways of showing this:]

Consider two vertices. If the probability of chosing each one of them is less
than 1/2 then both will be chosen less than 1/4 of the time, which means that
3/4 of the time we added the correct number to value of the coverage and 1/4 of
the time we got a spurious score of 2 in the objective function since y(u,v)=0
yet we double count both vertices. 

This means that the expected value of the objective function here is

      3/4 x 1 + 1/4 x 2 = 5/4

I.e. we on the expectation within 5/4 of the actual optimal integer value.

Now, if the probabilities of taking each of the vertices add to more than one
we then get that in the expected contribution to the objective function because
of double covering is

(1-c^2) + (3 - 2c) * c^2
 
where the worst case occurs when both points have a probability of c=35/27 for
an expected value of 0.77 > 3/4 of opt.

Q4

Run A to obtain a solution and then verify using the procedure, then after time
T(n) + t(n) we have a correct solution with probability gamma(n). Alternatively,
with probability (1- gamma(n)),  A fails and we repeat the combination run. Once
again with probability gamma(n) we succeed. So the expected running time is

T(n) + t(n)+(1- gamma(n) )(T(n) + t(n))+ (1-gamma(n))^2(T(n)+t(n))+...

After we factor out T(n) + t(n), this is an infinite series of the form sum x_i
which equals 1/(1-x). Substituting x=1-gamma(n) we get 

(T(n) + t(n)) x 1/gamma(n)

as claimed.

Q5


The solution is to execute the algorithm at increasing lengths of time,
starting with 1, 2, 4, 8, ...  until interrupted. In the worst case the
interruption happens at time N=2^i-1-epsilon. The algorithm is about to
complete a program of length 2^(i-1) when this interruption takes place, and hence
the quality of the best solution computed is 2(i-2). I.e., we have a solution of
quality Q(N/4).